package 华为OD机试真题2023.进阶题;

import utils.MyUtil;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

public class HJ34_天然蓄水库 {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(new File("src/main/java/华为OD机试真题2023/进阶题/input/34.txt"));
        MyUtil.START();
        Solution(in);
        //        Solution2(in);
        MyUtil.END();
    }

    static void Solution(Scanner in) {
        String[] sArray = in.nextLine().split(" ");
        int len = sArray.length;
        int[] height = new int[len];
        for (int i = 0; i < len; i++) {
            height[i] = Integer.parseInt(sArray[i]);
        }
        int[] max_left = new int[len];
        int[] max_right = new int[len];
        for (int i = 1; i < len; i++) {
            max_left[i] = Math.max(max_left[i - 1], height[i - 1]);
        }
        for (int i = len - 2; i >= 0; i--) {
            max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
        }
        int[] waterAndMountain = new int[len];
        Set<Integer> wanted = new HashSet<>();
        for (int i = 1; i < len - 1; i++) {
            int water = Math.max(0, Math.min(max_left[i], max_right[i]) - height[i]);
            if (water > 0) {
                waterAndMountain[i] = water + height[i];
                wanted.add(waterAndMountain[i]);
            }
        }
        int[] result = new int[3];
        for (int want : wanted) {
            int left = 0;
            int right = len - 1;
            while (waterAndMountain[left] < want || height[left] >= want) {
                left++;
            }
            while (waterAndMountain[right] < want || height[right] >= want) {
                right--;
            }
            int total = 0;
            for (int i = left; i <= right; i++) {
                total += Math.max(want - height[i], 0);
            }
            left--;
            right++;
            if (total > result[2]) {
                result[0] = left;
                result[1] = right;
                result[2] = total;
            } else if (total == result[2]) {
                if (right - left < result[1] - result[0]) {
                    result[0] = left;
                    result[1] = right;
                    result[2] = total;
                }
            }
        }
        if (result[2] == 0) {
            System.out.println(0);
        } else {
            System.out.println(result[0] + " " + result[1] + ":" + result[2]);
        }
    }

    static void Solution2(Scanner input) {
        // 山脉的高度数组
        Integer[] height =
                Arrays.stream(input.nextLine().split(" "))
                        .map(Integer::parseInt)
                        .toArray(Integer[]::new);
        int n = height.length;
        // 左侧最高山脉数组
        int[] left = new int[n];
        for (int i = 1; i < n; i++) {
            // i左侧的最高山脉
            left[i] = Math.max(left[i - 1], height[i - 1]);
        }
        // 右侧最高山脉数组
        int[] right = new int[n];
        for (int i = n - 2; i >= 0; i--) {
            // i右侧的最高山脉
            right[i] = Math.max(right[i + 1], height[i + 1]);
        }
        // 最大蓄水高度跟山脉的总高度数组
        int[] waterheight = new int[n];

        HashSet<Integer> waters_h = new HashSet<>();
        for (int i = 1; i < n - 1; i++) {
            // 当前山脉的最大蓄水量
            int wat = Math.max(0, Math.min(left[i], right[i]) - height[i]);
            if (wat != 0) {
                // 最大蓄水量的高度+山脉的高度
                waterheight[i] = wat + height[i];
                waters_h.add(waterheight[i]);
            }
        }

        int[] result = new int[3];

        for (int sig : waters_h) {
            // 左侧第一个满足条件的山脉
            int l = 0;
            while (waterheight[l] < sig || height[l] >= sig) {
                l++;
            }
            // 右侧第一个满足条件的山脉
            int r = n - 1;
            while (waterheight[r] < sig || height[r] >= sig) {
                r--;
            }
            // 蓄水量求和
            int total_wat = 0;
            for (int i = l; i <= r; i++) {
                total_wat += Math.max(0, sig - height[i]);
            }
            if (total_wat > result[2]) {
                // 蓄水量大于之前的最大蓄水量则重置左右山脉索引和最大蓄水量
                result[0] = l - 1;
                result[1] = r + 1;
                result[2] = total_wat;
            } else if (total_wat == result[2]) {
                // 蓄水量等于之前最大蓄水量则判断其山脉距离，选其距离较小的
                int d = r - l + 1;
                int d2 = result[1] - result[0] - 1;
                if (d < d2) {
                    result[0] = l - 1;
                    result[1] = r + 1;
                }
            }
        }
        if (result[2] == 0) {
            System.out.print(0);
        } else {
            System.out.print(result[0]);
            System.out.print(" ");
            System.out.print(result[1]);
            System.out.print(":");
            System.out.print(result[2]);
        }
    }
}
